package com.itheima.recursion_multi;

/**
 * 杨辉三角
 *
 * @FileName E03PascalTriangle
 * @Description
 * @Author Sword
 * @date 2025-03-17
 **/
public class E03PascalTriangle {

    /**
     * 杨辉三角（未优化）
     *
     * @param i
     * @param j
     * @return
     */
    private static int element1(int i, int j) {
        if (j == 0 || j == i) {
            return 1;
        }
        return element1(i - 1, j - 1) + element1(i - 1, j);
    }

    private static void print1(int n) {
        for (int i = 0; i < n; i++) {
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element1(i, j));
            }
            System.out.println();
        }
    }


    /**
     * 杨辉三角（二维数组记忆法优化）
     *
     * @param triangle
     * @param i
     * @param j
     * @return
     */
    private static int element2(int[][] triangle, int i, int j) {
        if (triangle[i][j] > 0) {
            return triangle[i][j];
        }
        if (j == 0 || j == i) {
            triangle[i][j] = 1;
            return 1;
        }
        triangle[i][j] = element2(triangle, i - 1, j - 1) + element2(triangle, i - 1, j);
        return triangle[i][j];
    }

    private static void print2(int n) {
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            triangle[i] = new int[i + 1];
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element1(i, j));
            }
            System.out.println();
        }
    }

    /*
        0   0   0   0   0   0   初始状态
        1   0   0   0   0   0   i = 0
        1   1   0   0   0   0   i = 1
        1   2   1   0   0   0   i = 2
        1   3   3   1   0   0   i = 3
        1   4   6   4   1   0   i = 4
     */

    /**
     * 杨辉三角（一维数组记忆法优化）
     *
     * @param row
     * @param i
     */
    private static void createRow(int[] row, int i) {
        if (i == 0) {
            row[0] = 1;
            return;
        }

        for (int j = i; j > 0; j--) {
            row[j] = row[j] + row[j - 1];
        }
    }

    private static void print3(int n) {
        int row[] = new int[n];
        for (int i = 0; i < n; i++) {
            createRow(row, i);
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", row[j]);
            }
            System.out.println();
        }
    }

    private static void printSpace(int n, int i) {
        int num = (n - 1 - i) * 2;
        for (i = 0; i < num; i++) {
            System.out.print(" ");
        }
    }

    public static void main(String[] args) {
//        print1(10);
//        print2(10);
        print3(10);
    }
}
